Implementation Templates (Cheat-Sheet)

Keep these minimal snippets handy for assignments.

The key takeaway is to start from a reliable template, then adapt it to the specific problem requirements.
BFS uses a queue (first-in, first-out) to explore level by level.
DFS uses a stack (last-in, first-out) to explore as deeply as possible along each branch.
In Python, collections.deque is highly efficient for both. Use popleft() for a queue (BFS) and pop() for a stack (DFS).
In C++, use std::queue for BFS and std::stack for DFS. In C, you'd typically implement these data structures using a dynamically-sized array or a linked list.

# BFS template def bfs_template(G, s): from collections import deque q, visited = deque([s]), {s} parent, level = {s: None}, {s: 0} while q: u = q.popleft() for w in G[u]: if w not in visited: visited.add(w) parent[w] = u level[w] = level[u] + 1 q.append(w) return parent, level

# DFS template (iterative) def dfs_template(G, s): visited, parent = set(), {s: None} stack = [s] while stack: u = stack.pop() if u in visited: continue visited.add(u) for w in reversed(G[u]): if w not in visited: parent[w] = u stack.append(w) return parent, visited